Всех приветствую. Сегодня мы разберем несколько интересных задач, которые запросто могут вам попасться на собеседованиях в таких фирмах, как Яндекс, Сбер, Тинькофф и другие. Сразу предупрежу, на платформе Leetcode эти задачи оценивались бы как Medium сложности, однако сложного тут ничего нет. Каждую из них с небольшой подготовкой может решить каждый.
Первую задачу я разберу максимально подробно, однако остальные задачи вам придется разбирать самостоятельно. Их разборы вы можете найти на ютубе яндекс - разборов. Интересно? Тогда вам по ссылкам ниже:
Порядок решения любой задачи (с примером)...
Ладно, так уж и быть, расскажу я вам, каким образом именно нужно мыслить, когда вы решаете задачи (мое субъективное мнение).
Давайте рассмотрим одну из задач, которая однажды мне НЕ попалась на собесе в Яндекс. (СОВЕРшЕННО СЛУЧАЙНАЯ ЗАДАЧА НЕ С ЯНДЕКСА)
На вход подается массив, состоящий только из чисел. Вам необходимо вывести строку, которая перечислит через запятую все диапазоны чисел, причем в порядке возрастания.
Пример:
[1,0,2,3,5] -> "0-3,5"
[3,6,5,4,9,8,0] -> "0,3-6,8-9"
[3,2] ->"2,3"
- Как только вам дали задачу, не торопитесь, потому что вам с самого начало нужно придумать наилучшую тактику ее решения, а потом ее уже делать. Иначе вы потратите свое время понапрасну.
Придумайте, как вам приблизиться к решению...
Для начала давайте откопаем простые находки, которые помогут на в решении задачи.
Если начать копаться, то можно обратить внимание на формат ответа, который нас интересует. Так как на выходе нас просят строку, то ответ задачи - строка. Если же на вход нам дают не строку, а список, то, скорее всего, мы должны будем как-то преобразовать список в строку. Как раз для такого случая существует метод .join(), который способен объединить все элементы списка в строку, используя конкретный разделитель.
Давайте вспомним, как он работает:
names=['Сережа','Вася','Петя','Коля']
print("; ".join(names)) # -> "Сережа; Вася; Петя; Коля"
Вернемся к нашей задаче.
От нас требуют вид ответа "0,3-6,8-9", значит мы можем сначала создать список, для данного примера вида ['0',"3-6","8-9"], а потом использовать метод ",".join(['0',"3-6","8-9"]), то есть разделим такие строки в списке между собой с помощью запятых.
Теперь используем то, что уже имеем, а именно:
- Мы должны получить список вида
['0',"3-6","8-9"]
Заметим, что в этом списке все числа как бы отсортированы, а значит нам для начала придется, хотим мы этого или нет, отсортировать начальный список.
Дело в том, что если мы хотим создать такой список быстро, то мы будем просто .append-ить в список данные строки. То есть сначала ноль, потом диапазон 3-6, потом 8-9. А это в свою очередь значит, что мы сначала должны будем найти 0, потом числа больше 0, и так далее. Всё это намекает на отсортированный список
Думаю, всем нам ясно, что сортировать начальный список мы будем не в конце программы, а в ее начале, потому что нам нужно сразу же избавиться от этой проблемы. Можно сортировать по разному, в нашем случае это встроенная функция sorted()
Оцените сложность такого решения...
На самом деле это самая главная ошибка любого новичка - НЕ оценивать сложность своего решения.
Впервые с этой проблемой столкнулись в 20 веке, когда мощности машин были на ничтожном уровне. Скорости у машин были маленькие, и необходимо было максимально оптимизировать свой код. И именно тогда обнаружили в таких небольших задачах как наша, что при определенных ситуациях она начинает тратить слишком много времени. Всё дело в том, что если задача имеет, к примеру, сложность O(N^2) (Обычно это происходит когда каждый элемент массива проверяется с каждым другим элементом массива. Если в массиве 100 элементов, то каждый будет сверяться с каждым, что даст нам 100*100=10000 операций. Про остальное можете прочитать сами)
Хорошо, но как нам понять, какая сложность нам нужна?
- Сразу тяжело дать ответ на этот вопрос, но в подобного рода задачах ответ обычно либо O(N) либо O(N logN).
- Присмотритесь, мы уже добавили в задачу такой элемент как сортировка. Теоретически доказано, что максимально возможная скорость сортировки массива имеет сложность O(N log N), а значит не видать нам O(N). Но это не критично, к тому же мы точно знаем что без сортировки никак. Поехали дальше.
Начните писать код, опираясь на необходимую сложность программы...
Отлично! У нас уже появился начальный каркас решения задачи. Давайте его запишем.
def arr_range(arr:list[int]) -> str: # На вход дают лист из чисел, на выходе строку
q=sorted(arr) # Отсортировали список
ans=[] # В этот список будем записывать все наши строки
# Должен быть return ','.join(ans)
- Теперь мы точно знаем, что у нас есть отсортированный массив. Дальше нам просто нужно находить диапазоны, если нет, то отдельные числа, и записывать их в виде строк в список
ans
Предлагаю дальше самостоятельно попробовать свои силы.
Мой же код ниже:
def arr_range(arr:list[int]) -> str: # На вход дают лист из чисел, на выходе строку
q=sorted(arr) # Отсортировали список
ans=[] # В этот список будем записывать все наши строки
if len(q)==0:
return ""
if len(q)==1:
return q[0]
start=0
last=start
for i in range(len(q)-1):
a=q[i]
b=q[i+1]
if b-a==1:
last+=1
if i==len(q)-2:
ans.append(f"{q[start]}-{q[last]}")
else:
if start==last:
ans.append(str(a))
else:
ans.append(f"{q[start]}-{q[last]}")
start=i+1
last=start
if i==len(q)-2:
ans.append(str(b))
return ','.join(ans)
print(arr_range([0,1,2,5,3,7,6,9]))
print(arr_range([0,1]))
print(arr_range([0,2]))
print(arr_range([1,2,3,4,7,8,10,11]))
print(arr_range([]))
На выходе получаем нужные результаты:
0-3,5-7,9
0-1
0,2
1-4,7-8,10-11
<-тип пустая строка
Условия и решения остальных задач...
Задача №1...
На вход дается строка. Выведите самый длинный палиндром, который в расположен в данной строке.
Ниже привожу два различных решения (одно длинное, другое короткое из-за использования особенностей некоторых функций)
def long_palindrom(self,s:str)->str:
def palindromer(s,x,y):
# print(x,y,end=' ')
if x < 0 or y>len(s)-1:
return s[x+1:y],y-x-1
if s[x]==s[y]:
if x == 0 or y==len(s)-1:
# print(s[x:y+1],y-x+1,"Дошли до конца",type(s),type(y-x+1))
return s[x:y+1],y-x+1
# print('идем дальше',s[x:y+1],x,y)
x-=1
y+=1
p,t=palindromer(s,x,y)
return p,t
else:
# print(s[x+1:y],y-x-1,"Не совпадает,",type(s),type(y-x+1))
return s[x+1:y],y-x-1
q=s.lower()
del_s=",. "
for letter in del_s:
q=q.replace(letter,'')
if len(q)==1:
return q
max_arr=[]
max_len=0
for i in range(0,len(q)):
arr,cur_len=palindromer(q,i-1,i+1)
if cur_len>=max_len:
max_len=cur_len
max_arr=arr
for i in range(1,len(q)):
arr,cur_len=palindromer(q,i-1,i)
if cur_len>=max_len:
max_len=cur_len
max_arr=arr
return max_arr
def long_palindrom_2(self, s: str) -> str:
def palindromer(l,r):
while (l>=0) and (r<n) and (s[l]==s[r]):
l-=1
r+=1
return s[l+1:r]
max_arr = ""
for i in range(len(s)):
max_arr = max(max_arr, palindromer(i,i), palindromer(i, i+1), key=lambda x: len(x)) # Нахождение самого длинного палиндрома
return max_arr
Задача №2...
Есть некая строка s, состоящая из различных символов
Найти максимально длинную подстроку, состоящую из уникальных симоволов, т.е. без повторений
class Solution:
def understr(self, a: str) -> str:
temp=[]
maxy=[]
n_maxy=0
n=0
for letter in a:
if letter not in temp:
temp.append(letter)
n+=1
else:
if n>=n_maxy:
maxy=temp
n_maxy=n
n=0
temp=[letter]
return ''.join(maxy)
Задача №0...
(Из литкода easy задача чисто ради решения нового посмотреть)
Ссылка на задачу: Перейти
The Two Sum problem asks us to find two numbers in an array that sum up to a given target value. We need to return the indices of these two numbers.
Approach...
- One brute force approach is to consider every pair of elements and check if their sum equals the target. This can be done using nested loops, where the outer loop iterates from the first element to the second-to-last element, and the inner loop iterates from the next element to the last element. However, this approach has a time complexity of O(n^2).
- A more efficient approach is to use a hash table (unordered_map in C++). We can iterate through the array once, and for each element, check if the target minus the current element exists in the hash table. If it does, we have found a valid pair of numbers. If not, we add the current element to the hash table.
Approach using a hash table:
- Create an empty hash table to store elements and their indices.
- Iterate through the array from left to right.
- For each element nums[i], calculate the complement by subtracting it from the target: complement = target - nums[i].
- Check if the complement exists in the hash table. If it does, we have found a solution.
- If the complement does not exist in the hash table, add the current element nums[i] to the hash table with its index as the value.
- Repeat steps 3-5 until we find a solution or reach the end of the array.
- If no solution is found, return an empty array or an appropriate indicator.
This approach has a time complexity of O(n) since hash table lookups take constant time on average. It allows us to solve the Two Sum problem efficiently by making just one pass through the array.
Перевод...
Интуиция
Задача о двух суммах требует от нас найти в массиве два числа, сумма которых равна заданному целевому значению. Нам нужно вернуть индексы этих двух чисел.
Подход
Один из подходов грубой силы заключается в рассмотрении каждой пары элементов и проверке, равна ли их сумма целевому значению. Это можно сделать с помощью вложенных циклов, где внешний цикл выполняет итерацию от первого элемента к предпоследнему элементу, а внутренний цикл выполняет итерацию от следующего элемента к последнему элементу. Однако этот подход имеет временную сложность O (n ^ 2).
Более эффективным подходом является использование хэш-таблицы (unordered_map в C++). Мы можем выполнить итерацию по массиву один раз и для каждого элемента проверить, существует ли целевой минус текущий элемент в хэш-таблице. Если это так, то мы нашли правильную пару чисел. Если нет, мы добавляем текущий элемент в хэш-таблицу.
Подход с использованием хэш-таблицы:
Создайте пустую хэш-таблицу для хранения элементов и их индексов.
Выполните итерацию по массиву слева направо.
Для каждого элемента nums[i] вычислите дополнение, вычитая его из целевого значения: дополнение = целевое значение - nums[i].
Проверьте, существует ли дополнение в хэш-таблице. Если это так, то мы нашли решение.
Если дополнение не существует в хэш-таблице, добавьте текущий элемент nums[i] в хэш-таблицу с его индексом в качестве значения.
Повторяйте шаги 3-5, пока мы не найдем решение или не дойдем до конца массива.
Если решение не найдено, верните пустой массив или соответствующий индикатор.
Этот подход имеет временную сложность O (n), поскольку поиск по хэш-таблице в среднем занимает постоянное время. Это позволяет нам эффективно решить задачу о двух суммах, выполнив всего один проход по массиву.
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
n = len(nums)
for i in range(n - 1):
for j in range(i + 1, n):
if nums[i] + nums[j] == target:
return [i, j]
return [] # No solution found
Solution 2: (Two-pass Hash Table)...
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
numMap = {}
n = len(nums)
# Build the hash table
for i in range(n):
numMap[nums[i]] = i
# Find the complement
for i in range(n):
complement = target - nums[i]
if complement in numMap and numMap[complement] != i:
return [i, numMap[complement]]
return [] # No solution found
Solution 3: (One-pass Hash Table)...
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
numMap = {}
n = len(nums)
for i in range(n):
complement = target - nums[i]
if complement in numMap:
return [numMap[complement], i]
numMap[nums[i]] = i
return [] # No solution found